Méthodes par différences temporelles n-Step (n-step TD Methods)

4.Apprentissage de type Off-policy avec les méthodes n-step

Principe de fonctionnement

Pour rappel, l'apprentissage de type Off-policy consiste à apprendre une fonction des valeurs d'actions d'une stratégie $\pi$, alors que l'exploration se fait à l'aide d'une autre stratégie, $b$. Souvent, $\pi$ est une stratégie optimale par rapport à la fonction des valeurs d'actions courante, alors que $b$ est davantage exploratrice, comme par exemple de type ɛ-greedy.

Pour pouvoir utiliser les données obtenues avec $b$ avec $\pi$, il faut prendre en compte les différences entre les deux stratégies. Cela se fait en considérant leurs probabilités respectives sur les actions qui ont été prises. Dans les méthodes n-step, les revenus sont construits à travers n pas de temps, on a donc besoin des probabilités relatives sur ces $n$ actions.

Par exemple, pour réaliser une version Off-policy d'une méthode n-step, une mise à jour à l'instant $t$ (et donc réalisée à l'instant $t+n$) peut se faire en utilisant le ratio d'échantillonnage préférentiel obtenu sur cette intervalle:

$${V_{t + n}}\left( {{S_t}} \right) = {V_{t + n - 1}}\left( {{S_t}} \right) + \alpha {\rho _{t:t + n - 1}}\left[ {{G_{t:t + n}} - {V_{t + n - 1}}\left( {{S_t}} \right)} \right], \quad 0 \le t \le T$$

avec ${\rho _{t:t + n - 1}}$ le ratio d'échantillonnage préférentiel décrivant le rapport des probabilités de prendre les $n$ actions entre les deux stratégies, depuis l'état $S_t$ jusqu'à l'état $S_{t+n}$ ($A_t$ à $A_{t+n-1}$) :

$${\rho _{t:h}} = \prod\limits_{k = t}^{\min \left( {h,T - 1} \right)} {\frac{{\pi \left( {{A_k}|{S_k}} \right)}}{{b\left( {{A_k}|{S_k}} \right)}}}$$

L'équation permettant d'obtenir la valeur des actions peut être obtenue à partir de celle utilisée pour la méthode Sarsa n-step :

$${Q_{t + n}}\left( {{S_t},{A_t}} \right) = {Q_{t + n - 1}}\left( {{S_t},{A_t}} \right) + \alpha {\rho _{t + 1:t + n}}\left[ {{G_{t:t + n}} - {Q_{t + n - 1}}\left( {{S_t},{A_t}} \right)} \right], \quad 0 \le t \le T$$

Remarquons ici que le calcul du ratio d'échantillonnage préférentiel se fait un pas de temps après ce qui se fait pour le calcul des valeurs des états avec les méthodes n-step TD. Cela vient du fait qu'ici on met à jour les paires d'états-actions. Il n'est donc pas utile de savoir la probabilité d'avoir pris l'action, mais plutôt de savoir ce qui adviendra après l'avoir choisie en ne prenant en compte via le ratio d'échantillonnage préférentiel que les actions à venir.

Algorithme